import java.util.*;
/**
 * Created with IntelliJ IDEA.
 * Description: 动态规划算法练习
 */
public class Test {
    public static void main(String[] args) {
        System.out.println(minCut("aab"));
    }
    public static void main1(String[] args) {
        int[][] num = {{2},{3, 4},{6, 5, 7},{4, 2, 8, 3}};
        int ret = minTrace3(num);
        System.out.println(ret);
    }

    /**
     * 给定一个字符串s和一组单词dict，判断s是否可以用空格分割成一个单词序列
     * 使得单词序列中所有的单词都是dict中的单词（序列可以包含一个或多个单词）
     * 例如:
     * 给定s=“nowcode”；
     * dict=["now", "code"].
     * 返回true，因为"nowcode"可以被分割成"now code"
     * @param s
     * @param dict
     * @return
     */
    public boolean wordBreak(String s, Set<String> dict) {
        // dp解法
        // 问题是判断前 len 个字符是否可分
        // 可以将问题分解为遍历 0 ~ len - 1
        // 然后判断前 i 个字符是否可分 && i + 1 ~ len之间是否能在dict中找到
        // F[i] && s.substring(i + 1, len)
        // 那么问题就成了求前 i 个字符是否可分...
        // F[j] && s.substring(j + 1, i)
        // 因此我们需要保存的中间值就是 前 i 个数据是否可分的true/false
        // 追溯到开头，前 0 个字符是否可分和 0~1之间是否能在dict中找到
        // 因此状态初始化就是 F[0] = true;
        int length = s.length();
        boolean[] F = new boolean[length + 1];
        F[0] = true;
        // 状态定义：F(length)
        // 状态间的转移方程定义：F[j] && dict.contains(s.subString(j,i));
        // 状态转移方程表示 判断前 j 个数是否能分和j~i之间的字符串能否在dict中找到
        // 状态的初始化：F[0] = true;
        // 返回结果：F(length)
        //大循环每循环一次都是判断前i个字符能否被分
        for(int i = 1; i <= length; i++) {
            for(int j = 0; j < i; j++) {
                if(F[j] && dict.contains(s.substring(j + 1,i))) {
                    F[i] = true;
                    break;
                }
            }
        }
        return F[length];
    }

    /**
     * 三角形最小路径和
     * 动态规划方法求解方法一：创建数组，遍历到哪一层，就保存到那一层每个元素的最小路径和
     * 空间复杂度：O(N) 创建一个数组来保存最小路径值
     * 时间复杂度：O(N) 每个位置的元素最多访问两次
     * @param triangle
     * @return
     */
    public static int minTrace(int[][] triangle) {
        // write code here
        //典型动态规划dp问题
        //状态定义：ret[j] = 从tri[0][0]——tri[i][j]的最小路径和
        //状态转移方程：
        //int temp1 = ret[j - 1] + triangle[i][j]
        //int temp2 = ret[j] + triangle[i][j]
        //ret[j] = temp1 < temp2 ? temp1 : temp2;
        //状态的初始值 ret[0] = triangle[0][0];
        //返回结果 ret[min]

        //1.创建一个triangle长度的数组
        int length = triangle.length;
        int[] ret = new int[length];
        ret[0] = triangle[0][0];
        for(int i = 1; i < length; i++) {
            //注意这里 j 的值必须从 i 开始减小
            //因为每次存储新的ret[j]的最短路径，都会覆盖之前的
            //ret[j]需要用到ret[j - 1]的数据
            //就需要保证ret[j - 1]要比ret[j]修改的要晚
            for(int j = i; j >= 0; j--) {
                int temp1 = 0;
                int temp2 = 0;
                //判断是否是一维数组的第一个元素
                if(j - 1 < 0) {
                    temp1 = 10000 + triangle[i][j];
                }else {
                    temp1 = ret[j - 1] + triangle[i][j];
                }
                //判断是否是一维数组的最后一个元素
                if(j == i) {
                    temp2 = 10000 + triangle[i][j];
                }else {
                    temp2 = ret[j] + triangle[i][j];
                }
                if(temp1 < temp2) {
                    ret[j] = temp1;
                }else {
                    ret[j] = temp2;
                }
            }
        }
        int min = ret[0];
        for(int i = 1; i < length; i++) {
            if(min > ret[i]) {
                min = ret[i];
            }
        }
        return min;
    }

    /**
     * 三角形最小路径和
     * 动态规划方法求解方法二：
     * 在数组中直接保存从triangle[0][0] ~ triangle[i][j]之间的最小路径之和
     * 空间复杂度：O(1) 会破坏原二维数组的值
     * 时间复杂度：O(N) 与方法一一致
     * @param triangle
     * @return
     */
    public int minTrace2 (int[][] triangle) {
        // write code here
        //状态定义：triangle[i][j] = triangle[0][0] ~ triangle[i][j]之间的最小路径和
        //状态转移方程：
        //triangle[i][j] = Math.min(triangle[i - 1][j - 1] + triangle[i][j],
        //                                      triangle[i - 1][j] + triangle[i][j])
        //状态的初始值triangle[0][0];
        //返回结果 min(triangle[len - 1][j])
        int length = triangle.length;
        for(int i = 1; i < length; i++) {
            for(int j = 0; j <= i; j++) {
                //注意，当j == 0 || j == i时，处于边界条件，且只有一条路径可选，因此特殊处理
                if(j == 0) {
                    triangle[i][j] = triangle[i - 1][j] + triangle[i][j];
                }else if(j == i) {
                    triangle[i][j] = triangle[i - 1][j - 1] + triangle[i][j];
                }else {
                    triangle[i][j] = Math.min(triangle[i - 1][j - 1] +
                            triangle[i][j], triangle[i - 1][j] + triangle[i][j]);
                }
            }
        }
        int min = triangle[length - 1][0];
        for(int i = 1; i < length; i++) {
            if(min > triangle[length - 1][i]) {
                min = triangle[length - 1][i];
            }
        }
        return min;
    }

    /**
     * 三角形最小路径和
     * 动态规划方法求解方法三：
     * 从上往下的递归动态方法
     * 递归次数太多，时间复杂度会非常高，会超时
     * @param triangle
     * @return
     */
    public static int minTrace3(int[][] triangle) {
        // write code here
        //状态定义：triangle[i - 1][j - 1] || triangle[i - 1][j] ~ triangle[i][j]之间的最小路径
        //状态转移方程：
        //ret = dp(int[][] triangle, i, j) //表示从triangle[0][0]到triangle[i][j]之间的最小路径和
        //if(min > ret) min = ret;
        //状态的初始值triangle[0][0];
        //返回结果 min
        int min = 1000_000_000;
        int length = triangle.length;
        for(int i = 0; i < length; i++) {
            int ret = dp(triangle, length - 1, i);
            if(min > ret) {
                min = ret;
            }
        }
        return min;
    }

    public static int dp(int[][] triangle,int i,int j) {
        if(i == 0 && j == 0) {
            return triangle[0][0];
        }
        if(i < 0 || j >= triangle[i].length || j < 0) {
            return 10_000_000;
        }
        int ret = Math.min(dp(triangle, i - 1, j), dp(triangle, i - 1, j - 1)) + triangle[i][j];
        return ret;
    }

    /**
     * 三角形最小路径和
     * 动态规划方法求解方法四：
     * 从下往上遍历
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * @param triangle
     * @return
     */
    public int minTrace4 (int[][] triangle) {
        // write code here
        //从下往上遍历
        //状态定义： triangle[i][j] ~ triangle[i + 1][j] || triangle[i + 1][j + 1]之间的最小路径
        //状态转移方程：
        //triangle[i][j] = Math.min(triangle[i + 1][j], triangle[i + 1][j + 1]) + triangle[i][j];
        //状态的初始值：最后一行的数据;
        //返回结果：triangle[0][0]
        int len = triangle.length;
        for(int i = len - 2; i >= 0; i--) {
            for(int j = 0; j <= i; j++) {
                triangle[i][j] = Math.min(triangle[i + 1][j], triangle[i + 1][j + 1]) + triangle[i][j];
            }
        }
        return triangle[0][0];
    }

    /**
     * 在m×n大小的地图的左上角（起点）
     * 机器人每次可以向下或向右移动。机器人要到达地图的右下角
     * 计算不同路径的数目
     * 方法一：从下往上，从右往左遍历
     * 由于状态是从1,1到m,n的路径的数量
     * 因此只有到了dp[m - 1][n - 1]的时候才是一条完整的路
     * 因此只有dp[m - 1][n - 1] = 1
     * 其他点的数量的计算
     * dp[i][j] = dp[i + 1][j] + dp[i][j + 1]
     * 就需要先计算下面的值和右边的值，就需要从下往上，从右往左遍历
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths (int m, int n) {
        // write code here
        //状态定义：从1,1到m,n的路径的数量
        //状态转移方程：
        //int dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
        //状态初值：dp[m - 1][n - 1] = 1;
        //返回结果：dp[0][0]
        int[][] dp = new int[m][n];
        dp[m - 1][n - 1] = 1;
        for(int i = m - 1; i >= 0; i--) {
            for(int j = n - 1; j >= 0; j--) {
                int tmp1 = 0;
                int tmp2 = 0;
                if(i + 1 < m) {
                    tmp1 = dp[i + 1][j];
                }
                if(j + 1 < n) {
                    tmp2 = dp[i][j + 1];
                }
                dp[i][j] = tmp1 + tmp2 + dp[i][j];
            }
        }
        return dp[0][0];
    }

    /**
     * 在m×n大小的地图的左上角（起点）
     * 机器人每次可以向下或向右移动。机器人要到达地图的右下角
     * 计算不同路径的数目
     * 方法二：从上往下，从左往右遍历
     * 由于从0,0位置水平方向的一行和竖直方向的一行只有一种情况
     * 因此可以先将dp[i][0] = 1,dp[0][j] = 1
     * 然后从1,1位置开始计算，就能保证每次上面和左边的位置可能的情况就提前计算过了
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths2 (int m, int n) {
        // write code here
        //状态定义：从1,1到m,n的路径的数量
        //状态转移方程：
        //int dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        //状态初值：dp[i][0] = 1,dp[0][j] = 0;
        //返回结果：dp[m - 1][n - 1]
        int[][] dp = new int[m][n];
        for(int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for(int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    /**
     * 给定一个由非负整数填充的m x n的二维数组，现在要从二维数组的左上角走到右下角
     * 请找出路径上的所有数字之和最小的路径
     * 注意：每次只能向下或向右移动
     * 与上一题类似
     * @param grid
     * @return
     */
    public int minPathSum (int[][] grid) {
        // write code here
        int row = grid.length;
        int line = grid[0].length;
        for(int i = 1; i < row; i++) {
            grid[i][0] += grid[i - 1][0];
        }
        for(int j = 1; j < line; j++) {
            grid[0][j] += grid[0][j - 1];
        }
        for(int i = 1; i < row; i++) {
            for(int j = 1; j < line; j++) {
                grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
            }
        }
        return grid[row - 1][line - 1];
    }

    /**
     * 01背包问题
     * 有N件物品和一个容量为V的背包
     * 第i件物品的价值是C[i]，重量是W[i]
     * 求解将哪些物品装入背包可使价值总和最大
     * 核心问题就是：
     * 每次都考虑这个物品能不能放入(背包空间是否足够)
     * 该不该放入(放入之后剩下背包空间的最优价值+自身价值 与 不放入该物品的最优价值进行比较)
     * 时间复杂度：O(N * V)
     * 空间复杂度：o(N * V)
     */
    public static void knapsack() {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            int N = sc.nextInt();
            int V = sc.nextInt();
            //状态定义：前 i 个物品，背包剩余容量为j，找最优的价值
            //状态转换方程：
            //if(j < weight[i]) value[i][j] = value[i - 1][j]
            //else value[i][j] = max(value[i - 1][j],
            //                 value[i - 1][j - weigth[i]] + goods[i])
            //状态初始值：
            //考虑0物品时的最优价值一定是0
            //考虑背包剩余空间为0时，最优价值也为0
            //value[i][0] = 0, value[0][j] = 0
            //返回结果：dp[N][V]
            int[] goods = new int[N + 1];
            int[] weight = new int[N + 1];
            for(int i = 1; i <= N; i++) {
                goods[i] = sc.nextInt();
                weight[i] = sc.nextInt();
            }
            //创建二维数组
            //保存剩余j个空间时考虑是否放入i才能得到的最优价值
            int[][] value = new int[N + 1][V + 1];
            for(int i = 0; i < N + 1; i++) {
                value[i][0] = 0;
            }
            for(int j = 0; j < V + 1; j++) {
                value[0][j] = 0;
            }
            for(int i = 1; i <= N; i++) {
                for(int j = 1; j <= V; j++) {
                    if(j < weight[i]) {
                        value[i][j] = value[i - 1][j];
                    }else {
                        value[i][j] = Math.max(value[i - 1][j], value[i - 1][j - weight[i]] + goods[i]);
                    }
                }
            }
            System.out.println(value[N][V]);
            //此时value[N][V]就是最优结果，逆推寻找具体是哪几个物品
            System.out.println(Arrays.toString(regain(value, weight)));
        }
    }

    public static int[] regain(int[][] value, int[] weight) {
        //value的数组长和宽都是多加了一个
        //因此此时要想得到实际背包容量和实际物品数量，应该 - 1
        int[] ret = new int[value.length - 1];
        int surplusWeight = value[0].length - 1;
        //i从物品数量开始递减
        int i = value.length - 1;
        while(i > 0) {
            if(value[i][surplusWeight] != value[i - 1][surplusWeight]) {
                //ret的长度只能是物品的数量，因此就要写成ret[i - 1] = 1
                //ret应该是从物品数量 - 1开始
                ret[i - 1] = 1;
                surplusWeight -= weight[i];
            }
            i--;
        }
        return ret;
    }

    /**
     * 01背包问题优化
     * 由于每次考虑放不放该物品，判断最优解的时候都是从上一行的最优解中拿数据
     * 因此我们仍然是逐行遍历，但是 j 从后往前进行考虑
     * 保证不会在使用上一行对应数据前对该数据修改
     * 这样操作之后
     * 优点：空间复杂度降为O(V)
     * 缺点：这样操作代码更不好理解，并且无法通过回溯判断最优情况下每种物品是否选择
     */
    public static void knapsack2() {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            int N = sc.nextInt();
            int V = sc.nextInt();
            //状态定义：前 i 个物品，背包剩余容量为j，找最优的价值
            //状态转换方程：
            //if(j < weight[i]) value[i][j] = value[i - 1][j]
            //else value[i][j] = max(value[i - 1][j],
            //                 value[i - 1][j - weigth[i]] + goods[i])
            //状态初始值：
            //考虑0物品时的最优价值一定是0
            //考虑背包剩余空间为0时，最优价值也为0
            //value[i][0] = 0, value[0][j] = 0
            //返回结果：dp[N][V]
            int[] goods = new int[N + 1];
            int[] weight = new int[N + 1];
            for(int i = 1; i <= N; i++) {
                goods[i] = sc.nextInt();
                weight[i] = sc.nextInt();
            }
            //简化，由于每次考虑放不放该物品，判断最优解的时候都是从上一行的最优解中拿数据
            //因此我们仍然是逐行遍历，但是 j 从后往前进行考虑
            //保证不会在使用上一行对应数据前对该数据修改
            //保存剩余j个空间时考虑是否放入i才能得到的最优价值
            int[] value = new int[V + 1];
            for(int i = 0; i < V + 1; i++) {
                value[i] = 0;
            }
            for(int i = 1; i <= N; i++) {
                for(int j = V; j >= 0; j--) {
                    if(j >= weight[i]){
                        value[j] = Math.max(value[j], value[j - weight[i]] + goods[i]);
                    }
                }
            }
            System.out.println(value[V]);
        }
    }

    /**
     * 分割回文串
     * 给出一个字符串s，分割s使得分割出的每一个子串都是回文串
     * 计算将字符串s分割成回文分割结果的最小切割数
     * 思路：
     * 从前往后，寻找前 i 个字符串的最小切割数
     * 首先先将每个位置都置为i - 1，因为之后每次都是和本位比较，得到最小值
     * 到第 i 个字符时，就要考虑前面是否有从 j 下标到 i 下标为回文串的可能
     * 如果j~i是回文串，count[i] = min(count[j - 1] + 1, count[i])
     * j 需要从1遍历到i，每轮都需要判断是否是回文串
     * 因为i与前面可能有多种切割方式，我们需要找到最优的那种
     * 比如：aaabbaaaaa，最优情况下应该是aaabbaaa aa，这种只需要切割一次
     * 最后count[N]就表示前 N 个字符的最小切割数
     *
     * 以上可以使用动态规划算法
     * 状态定义：count[i]的回文串的最少切割数
     * 状态转移方程：count[i] = min(count[j - 1] + 1, count[i])
     * 状态初始值：最差情况下，每个字符之间都需要分割，因此进行初始值赋值：count[i] = i - 1
     * 返回结果：count[N]
     * 时间复杂度：O(N ^ 3)
     * 空间复杂度：O(N)
     * @param s
     * @return
    */
    public boolean isSymmtric(int start,int end, String s) {
        while(start < end) {
            if(s.charAt(start++) != s.charAt(end--)) {
                return false;
            }
        }
        return true;
    }

    public int minCut (String s) {
        int len = s.length();
        int[] count = new int[len + 1];
        for(int i = 0; i <= len; i++) {
            count[i] = i - 1;
        }
        for(int i = 2; i <= len; i++) {
            for(int j = 1; j <= i; j++) {
                if(isSymmtric(j - 1, i - 1, s)) {
                    count[i] = Math.min(count[j - 1] + 1, count[i]);
                }
            }
        }
        return count[len];
    }

    /**
     * 编辑距离
     * 给定两个单词word1和word2，请计算将word1转换为word2至少需要多少步操作。
     * 你可以对一个单词执行以下3种操作：
     * a）在单词中插入一个字符
     * b）删除单词中的一个字符
     * c）替换单词中的一个字符
     * 时间复杂度：O(N ^ 2)
     * 空间复杂度；O(N * M)
     * @param word1
     * @param word2
     * @return
     */
    public int minDistance (String word1, String word2) {
        // write code here
        //状态定义：将word1转为word2的最少操作数
        //状态转移方程：
        //if(word1[i] == word2[j]) dp[i][j] = dp[i - 1][j - 1]
        //else min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1)
        //状态初始化：dp[i][0] = i dp[0][j] = j
        //返回值:dp[N][M]
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        for(int i = 0 ; i <= len1; i++) {
            dp[i][0] = i;
        }
        for(int i = 0 ; i <= len2; i++) {
            dp[0][i] = i;
        }
        for(int i = 1; i <= len1; i++) {
            for(int j = 1; j <= len2; j++) {
                if(word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                    continue;
                }
                dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + 1);
            }
        }
        return dp[len1][len2];
    }

    /**
     * 不同的子序列
     * 给定两个字符串S和T，返回S子序列等于T的不同子序列个数有多少个？
     * 字符串的子序列是由原来的字符串删除一些字符（也可以不删除）
     * 在不改变相对位置的情况下的剩余字符
     * （例如，"ACE"is a subsequence of"ABCDE"但是"AEC"不是）
     * 例如：
     * S="nowcccoder", T = "nowccoder"
     * 返回3
     *
     * 时间复杂度：O(N * M)
     * 空间复杂度：O(N * M)
     * @param S
     * @param T
     * @return
     */
    public int numDistinct (String S, String T) {
        // write code here
        //状态定义：S[1~i]的子串中有多少种情况等于T[1~j]
        //状态转移方程：
        //if(S[i] == T[j]) dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
        //else dp[i][j] = dp[i-1][j]
        //状态初始值：dp[i][0]都应该置为1，因为空串的情况只有一种
        //dp[0][i](i > 0)都置为0，因为S是空串，不可能存在子串能等于的情况
        //返回值：dp[N][M]
        int len1 = S.length();
        int len2 = T.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        for(int i = 0; i <= len1; i++) {
            dp[i][0] = 1;
        }
        for(int i = 1; i <= len1; i++) {
            for(int j = 1; j <= len2; j++) {
                if(S.charAt(i - 1) == T.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[len1][len2];
    }

    //这种写法的空间复杂度为O(N)，但是更加不好理解
    //如果是竞赛，推荐这种写法，如果是写代码，以容易理解的代码作为第一位
    public int numDistinct2 (String S, String T) {
        int len1 = S.length();
        int len2 = T.length();
        int[] dp = new int[len2 + 1];
        dp[0] = 1;
        for(int i = 1; i <= len1; i++) {
            for(int j = len2; j >= 1; j--) {
                if(S.charAt(i - 1) == T.charAt(j - 1)) {
                    dp[j] = dp[j] + dp[j - 1];
                }
            }
        }
        return dp[len2];
    }
}
